/*
 *                  Egothor Software License version 1.00
 *                  Copyright (C) 1997-2004 Leo Galambos.
 *               Copyright (C) 2002-2004 "Egothor developers"
 *                    on behalf of the Egothor Project.
 *                           All rights reserved.
 *
 * This  software  is  copyrighted  by  the "Egothor developers". If this
 * license applies to a single file or document, the "Egothor developers"
 * are the people or entities mentioned as copyright holders in that file
 * or  document.  If  this  license  applies  to the Egothor project as a
 * whole,  the  copyright holders are the people or entities mentioned in
 * the  file CREDITS. This file can be found in the same location as this
 * license in the distribution.
 *
 * Redistribution  and  use  in  source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 1. Redistributions  of  source  code  must retain the above copyright
 *    notice, the list of contributors, this list of conditions, and the
 *    following disclaimer.
 * 2. Redistributions  in binary form must reproduce the above copyright
 *    notice, the list of contributors, this list of conditions, and the
 *    disclaimer  that  follows  these  conditions  in the documentation
 *    and/or other materials provided with the distribution.
 * 3. The name "Egothor" must not be used to endorse or promote products
 *    derived  from  this software without prior written permission. For
 *    written permission, please contact Leo.G@seznam.cz
 * 4. Products  derived  from this software may not be called "Egothor",
 *    nor  may  "Egothor"  appear  in  their name, without prior written
 *    permission from Leo.G@seznam.cz.
 *
 * In addition, we request that you include in the end-user documentation
 * provided  with  the  redistribution  and/or  in the software itself an
 * acknowledgement equivalent to the following:
 * "This product includes software developed by the Egothor Project.
 *  http://egothor.sf.net/"
 *
 * THIS  SOFTWARE  IS  PROVIDED  ``AS  IS''  AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES,  INCLUDING,  BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY  AND  FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN  NO  EVENT  SHALL THE EGOTHOR PROJECT OR ITS CONTRIBUTORS BE LIABLE
 * FOR   ANY   DIRECT,   INDIRECT,  INCIDENTAL,  SPECIAL,  EXEMPLARY,  OR
 * CONSEQUENTIAL  DAMAGES  (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE  GOODS  OR  SERVICES;  LOSS  OF  USE,  DATA, OR PROFITS; OR
 * BUSINESS  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER  IN  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * This  software  consists  of  voluntary  contributions  made  by  many
 * individuals  on  behalf  of  the  Egothor  Project  and was originally
 * created by Leo Galambos (Leo.G@seznam.cz).
 */
package org.egothor.stemmer;

import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

/**
 * The MultiTrie is a Trie of Tries.
 *
 * <p>It stores words and their associated patch commands. The MultiTrie handles patch commands
 * broken into their constituent parts, as a MultiTrie does, but the commands are delimited by the
 * skip command.
 */
public class MultiTrie2 extends MultiTrie {
  /**
   * Constructor for the MultiTrie object.
   *
   * @param is the input stream
   * @exception IOException if an I/O error occurs
   */
  public MultiTrie2(DataInput is) throws IOException {
    super(is);
  }

  /**
   * Constructor for the MultiTrie2 object
   *
   * @param forward set to <code>true</code> if the elements should be read left to right
   */
  public MultiTrie2(boolean forward) {
    super(forward);
  }

  /**
   * Return the element that is stored in a cell associated with the given key.
   *
   * @param key the key to the cell holding the desired element
   * @return the element
   */
  @Override
  public CharSequence getFully(CharSequence key) {
    StringBuilder result = new StringBuilder(tries.size() * 2);
    try {
      CharSequence lastkey = key;
      CharSequence[] p = new CharSequence[tries.size()];
      char lastch = ' ';
      for (int i = 0; i < tries.size(); i++) {
        CharSequence r = tries.get(i).getFully(lastkey);
        if (r == null || (r.length() == 1 && r.charAt(0) == EOM)) {
          return result;
        }
        if (cannotFollow(lastch, r.charAt(0))) {
          return result;
        } else {
          lastch = r.charAt(r.length() - 2);
        }
        // key=key.substring(lengthPP(r));
        p[i] = r;
        if (p[i].charAt(0) == '-') {
          if (i > 0) {
            key = skip(key, lengthPP(p[i - 1]));
          }
          key = skip(key, lengthPP(p[i]));
        }
        // key = skip(key, lengthPP(r));
        result.append(r);
        if (key.length() != 0) {
          lastkey = key;
        }
      }
    } catch (IndexOutOfBoundsException _) {
    }
    return result;
  }

  /**
   * Return the element that is stored as last on a path belonging to the given key.
   *
   * @param key the key associated with the desired element
   * @return the element that is stored as last on a path
   */
  @Override
  public CharSequence getLastOnPath(CharSequence key) {
    StringBuilder result = new StringBuilder(tries.size() * 2);
    try {
      CharSequence lastkey = key;
      CharSequence[] p = new CharSequence[tries.size()];
      char lastch = ' ';
      for (int i = 0; i < tries.size(); i++) {
        CharSequence r = tries.get(i).getLastOnPath(lastkey);
        if (r == null || (r.length() == 1 && r.charAt(0) == EOM)) {
          return result;
        }
        // System.err.println("LP:"+key+" last:"+lastch+" new:"+r);
        if (cannotFollow(lastch, r.charAt(0))) {
          return result;
        } else {
          lastch = r.charAt(r.length() - 2);
        }
        // key=key.substring(lengthPP(r));
        p[i] = r;
        if (p[i].charAt(0) == '-') {
          if (i > 0) {
            key = skip(key, lengthPP(p[i - 1]));
          }
          key = skip(key, lengthPP(p[i]));
        }
        // key = skip(key, lengthPP(r));
        result.append(r);
        if (key.length() != 0) {
          lastkey = key;
        }
      }
    } catch (IndexOutOfBoundsException _) {
    }
    return result;
  }

  /**
   * Write this data structure to the given output stream.
   *
   * @param os the output stream
   * @exception IOException if an I/O error occurs
   */
  @Override
  public void store(DataOutput os) throws IOException {
    super.store(os);
  }

  /**
   * Add an element to this structure consisting of the given key and patch command.
   *
   * <p>This method will return without executing if the <code>cmd</code> parameter's length is 0.
   *
   * @param key the key
   * @param cmd the patch command
   */
  @Override
  public void add(CharSequence key, CharSequence cmd) {
    if (cmd.length() == 0) {
      return;
    }
    // System.err.println( cmd );
    CharSequence[] p = decompose(cmd);
    int levels = p.length;
    // System.err.println("levels "+key+" cmd "+cmd+"|"+levels);
    while (levels >= tries.size()) {
      tries.add(new Trie(forward));
    }
    CharSequence lastkey = key;
    for (int i = 0; i < levels; i++) {
      if (key.length() > 0) {
        tries.get(i).add(key, p[i]);
        lastkey = key;
      } else {
        tries.get(i).add(lastkey, p[i]);
      }
      // System.err.println("-"+key+" "+p[i]+"|"+key.length());
      /*
       * key=key.substring(lengthPP(p[i]));
       */
      if (p[i].length() > 0 && p[i].charAt(0) == '-') {
        if (i > 0) {
          key = skip(key, lengthPP(p[i - 1]));
        }
        key = skip(key, lengthPP(p[i]));
      }
      // System.err.println("--->"+key);
    }
    if (key.length() > 0) {
      tries.get(levels).add(key, EOM_NODE);
    } else {
      tries.get(levels).add(lastkey, EOM_NODE);
    }
  }

  /**
   * Break the given patch command into its constituent pieces. The pieces are delimited by NOOP
   * commands.
   *
   * @param cmd the patch command
   * @return an array containing the pieces of the command
   */
  public CharSequence[] decompose(CharSequence cmd) {
    int parts = 0;

    for (int i = 0; 0 <= i && i < cmd.length(); ) {
      int next = dashEven(cmd, i);
      if (i == next) {
        parts++;
        i = next + 2;
      } else {
        parts++;
        i = next;
      }
    }

    CharSequence[] part = new CharSequence[parts];
    int x = 0;

    for (int i = 0; 0 <= i && i < cmd.length(); ) {
      int next = dashEven(cmd, i);
      if (i == next) {
        part[x++] = cmd.subSequence(i, i + 2);
        i = next + 2;
      } else {
        part[x++] = (next < 0) ? cmd.subSequence(i, cmd.length()) : cmd.subSequence(i, next);
        i = next;
      }
    }
    return part;
  }

  /**
   * Remove empty rows from the given Trie and return the newly reduced Trie.
   *
   * @param by the Trie to reduce
   * @return the newly reduced Trie
   */
  @Override
  public Trie reduce(Reduce by) {
    List<Trie> h = new ArrayList<>();
    for (Trie trie : tries) h.add(trie.reduce(by));

    MultiTrie2 m = new MultiTrie2(forward);
    m.tries = h;
    return m;
  }

  private boolean cannotFollow(char after, char goes) {
    switch (after) {
      case '-':
      case 'D':
        return after == goes;
    }
    return false;
  }

  private CharSequence skip(CharSequence in, int count) {
    if (forward) {
      return in.subSequence(count, in.length());
    } else {
      return in.subSequence(0, in.length() - count);
    }
  }

  private int dashEven(CharSequence in, int from) {
    while (from < in.length()) {
      if (in.charAt(from) == '-') {
        return from;
      } else {
        from += 2;
      }
    }
    return -1;
  }

  @SuppressWarnings("fallthrough")
  private int lengthPP(CharSequence cmd) {
    int len = 0;
    for (int i = 0; i < cmd.length(); i++) {
      switch (cmd.charAt(i++)) {
        case '-':
        case 'D':
          len += cmd.charAt(i) - 'a' + 1;
          break;
        case 'R':
          len++; /* intentional fallthrough */
        case 'I':
          break;
      }
    }
    return len;
  }
}
